package com.yun.algorithmproblem.leetcodenotcomplete;

/**
 * 3176. 求出最长好子序列 I
 * <p>
 * 给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。
 * <p>
 * 请你返回 nums 中 好
 * 子序列
 * 的最长长度。
 */
public class Leetcode3176 {

    public static void main(String[] args) {
        Leetcode3176 leetcode3176 = new Leetcode3176();
        int n = 325;
        System.out.println(leetcode3176.countTwos(n));
        System.out.println(leetcode3176.countTwosByDigit(n));
        System.out.println(leetcode3176.countTwosInRange(1,n));
    }

    public int maximumLength(int[] nums, int k) {
        int length = nums.length;
        int p = 0, q = 0;
        int max = 1;
        int count = 0;
        return 0;
    }

    public int countTwos(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            int temp = i;
            while (temp > 0) {
                if (temp % 10 == 2) {
                    count++;
                }
                temp /= 10;
            }
        }
        return count;
    }

    public int countTwosByDigit(int n) {
        int count = 0;
        int digit = 1; // 用于处理每一位的权值（1，10，100，...）
        while (n / digit > 0) {
            int current = (n / digit) % 10;  // 当前位的数字
            int high = n / (digit * 10);     // 高位部分
            int low = n % digit;             // 低位部分
            // 先统一加上高位部分的贡献
            count += high * digit;
            // 接下来讨论当前位的影响
            if (current > 2) {
                count += digit; // 当前位大于2，说明可以加上 digit 次 2
            } else if (current == 2) {
                count += (low + 1); // 当前位是2，加上低位的贡献
            }
            digit *= 10; // 处理下一位
        }
        return count;
    }



    public long countTwosInRange(long start, long end) {
        if (start > end) return 0;

        long count = 0;
        long factor = 1; // 当前的数位因子，初始化为个位

        while (start * factor <= end) {
            long currEnd = end / factor;
            long currStart = (start - 1) / factor;

            // 处理当前数位上的2
            long countInDigit = currEnd - currStart;
            long countWithTwo = countInDigit / 10 * factor; // 不包含当前数位为2的

            // 当前数位为2的特殊情况
            long low = (currStart + 1) / 10 * 10 * factor;
            long high = (currEnd / 10 + 1) * 10 * factor - 1;
            if (low <= end) countWithTwo += Math.min(end - low + 1, factor);
            if (high >= start) countWithTwo -= Math.max(start - high - 1, 0);

            // 累加当前数位的结果
            count += countWithTwo;

            factor *= 10; // 移动到下一个数位
        }

        return count;
    }
}
